package a2_p04_ak_fh;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import javax.swing.tree.ExpandVetoException;

import org.jgrapht.WeightedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.WeightedMultigraph;

public class Astern {

	static Set<AttVertex> OL = null;
	static Set<AttVertex> CL = null;
	static int hits = 0;

	public static List<AttVertex> CalcA(
			WeightedGraph<AttVertex, DefaultWeightedEdge> graph,
			String startVertex, String endVertex) {

		GraphUtil gu = new GraphUtil();
		HashSet<AttVertex> allVertices = new HashSet<AttVertex>();
		AttVertex sVertex = null;
		AttVertex eVertex = null;
		AttVertex currVertex = null;
		hits = 0;

		if (graph instanceof WeightedMultigraph) {
			graph = gu.addUndirectedEdges(graph);
		}

		// Get Vertices
		for (DefaultWeightedEdge e : graph.edgeSet()) {
			allVertices.add(graph.getEdgeSource(e));
			allVertices.add(graph.getEdgeTarget(e));
		}

		// Find StartVertex and EndVertex
		for (AttVertex attVertex : allVertices) {
			if (attVertex.getName().equals(startVertex)) {
				currVertex = attVertex;
			}
			if (attVertex.getName().equals(endVertex)) {
				eVertex = attVertex;
			}
		}

		// OpenList
		OL = new HashSet<AttVertex>();
		// ClosedList
		CL = new HashSet<AttVertex>();

		// Attribute fuer Startknoten setzen und der offenen Liste hinzufuegen
		currVertex.setF(currVertex.getAttribute());
		currVertex.setG(0.0);
		currVertex.setVorg(currVertex);
		OL.add(currVertex);

		sVertex = currVertex;

		while (!OL.isEmpty()) {

			double minAttribute = Double.MAX_VALUE;

			// Knoten mit minimalem Attribut finden
			for (AttVertex attVertex : OL) {
				if (attVertex.getF() < minAttribute) {
					minAttribute = attVertex.getF();
					currVertex = attVertex;
				}
			}

			// Kleinsten Knoten in Closed List hinzufügen und aus der offenen
			// entfernen
			hits++;

			CL.add(currVertex);

			if (currVertex.equals(eVertex))
				return buildPath(sVertex, eVertex);

			expand(graph, currVertex);

			OL.remove(currVertex);

		}

		return null;

	}

	private static List<AttVertex> buildPath(AttVertex sVertex,
			AttVertex eVertex) {

		ArrayList<AttVertex> way = new ArrayList<AttVertex>();

		for (AttVertex attVertex : CL) {
			if (attVertex.equals(eVertex))
				eVertex = attVertex;
		}

		AttVertex currVertex = eVertex;

		while (currVertex != sVertex) {
			if (!way.contains(currVertex)) {
				way.add(currVertex);
			}
			currVertex = currVertex.getVorg();
		}

		way.add(currVertex);

		Collections.reverse(way);

		System.out.println("A*:");
		System.out.println("Kürzester Weg: " + way.toString());
		System.out.println(hits + " hits");
		System.out.println(eVertex.getG() + " wegl�nge");

		return way;
	}

	private static void expand(
			WeightedGraph<AttVertex, DefaultWeightedEdge> graph,
			AttVertex currVertex) {
		Set<DefaultWeightedEdge> touchingEdges = graph.edgesOf(currVertex);

		for (DefaultWeightedEdge e : touchingEdges) {

			AttVertex nextVertex = graph.getEdgeTarget(e);

			if (!nextVertex.equals(currVertex)) {

				if (!CL.contains(nextVertex)) {

					// gj > gk + lk,j
					if (nextVertex.getG() > (currVertex.getG() + graph.getEdgeWeight(e))) {
						nextVertex.setVorg(currVertex);
						// gj=gk+ik,j | Gewichtung setzen
						nextVertex.setG(currVertex.getG()+ graph.getEdgeWeight(e));
						// fj=gj+hj | Heuristik setzen
						nextVertex.setF(currVertex.getG()+ graph.getEdgeWeight(e)+ currVertex.getAttribute());
						OL.remove(nextVertex);
						OL.add(nextVertex);
					}
				}
			}
		}
	}

}
